// https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/
// Created by ade on 2022/10/28.
// "9,3,4,#,#,1,#,#,2,#,6,#,#"
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

class Solution {
public:
    void split(string str, const char splitChar, vector <string> &res) {
        istringstream iss(str);// 输入流
        string token; // 接受缓冲区
        while (getline(iss, token, splitChar)) {
            res.push_back(token);
        }
    }

    // 栈的方式
    bool isValidSerialization1(string preorder) {
        vector <string> arr;
        split(preorder, ',', arr);
        int len = arr.size();
        vector <string> st = {};
        for (int i = 0; i < len; i++) {
            st.push_back(arr[i]);
            int n = st.size();
            while (n >= 3 && st[n - 1] == "#" && st[n - 2] == "#" && st[n - 3] != "#") {
                st.pop_back();
                st.pop_back();
                st.pop_back();
                st.push_back("#");
                n = st.size();
            }
        }

        if (st.back() == "#") st.pop_back();
        return st.empty();
    }

    // 入度出度的方式
    bool isValidSerialization(string preorder) {
        vector <string> arr;
        split(preorder, ',', arr);
        int d = 1;
        for (auto &i:arr) {
            d--;
            if (d < 0) return false;
            if (i != "#") d += 2;
        }
        return d == 0;
    }
};

int main() {
    Solution so;
    string s = "9,3,4,#,#,1,#,#,2,#,6,#,#";
//    string s = "9,#,#,1";

    cout << so.isValidSerialization(s);
    return 0;
}